package com.dong.sortingAlgorithm;

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.HashMap;
import java.util.concurrent.atomic.AtomicInteger;

/*
快速排序
说白了就是给基准数据找其正确索引位置的过程.
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5,2,-6,9,7};
        quick_sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    public static void quick_sort(int[] s,int left,int right) {
        if (left < right) {
            //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换
            int i = left, j = right;
            int x = s[left]; //基准值
            //一次循环后，以基准值为准两边排序完
            while (i < j) {
                while (i < j && s[j] >= x) { // 从右向左找第一个小于x的数
                    j--;
                }
                if (i < j) {
                    s[i++] = s[j];
                }
                while (i < j && s[i] < x) { // 从左向右找第一个大于等于x的数
                    i++;
                }
                if (i < j) {
                    s[j--] = s[i];
                }
            }
            s[i] = x;  //将基准值填回去
            quick_sort(s, left, i - 1); // 递归调用
            quick_sort(s, i + 1, right);
            HashMap<Object, Object> map = new HashMap<>();
        }
        HashMap<Object, Object> map = new HashMap<>();

    }
}
